import heapq

class Graph:
    def __init__(self, n):
        self.n = n  # Number of vertices
        self.adj = [[] for _ in range(n + 1)]  # Adjacency list (1-indexed)

    def add_edge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)

def max_cut(graph, n):
    # Helper function to count cut edges
    def count_cut_edges(U):
        cut_edges = 0
        for u in range(1, n + 1):
            if U[u - 1] == 1:
                for v in graph.adj[u]:
                    if U[v - 1] == 0:
                        cut_edges += 1
        return cut_edges

    # Helper function for DFS-based bounding
    def dfs(node, U, visited, current_cut):
        visited[node] = True
        if U[node - 1] == 1:
            for neighbor in graph.adj[node]:
                if not visited[neighbor]:
                    current_cut += 1 - U[neighbor - 1]
                    dfs(neighbor, U, visited, current_cut)
        return current_cut

    # Initialize
    max_cut_edges = 0
    best_U = [0] * n

    # Priority queue (min-heap)
    pq = []
    initial_U = [1] * n  # Start with all vertices in U
    initial_cut = dfs(1, initial_U, [False] * (n + 1), 0)
    heapq.heappush(pq, (-initial_cut, initial_U[:]))

    while pq:
        current_cut, current_U = heapq.heappop(pq)
        current_cut = -current_cut  # Convert back to positive

        if current_cut > max_cut_edges:
            max_cut_edges = current_cut
            best_U = current_U[:]

        # Explore further by moving one vertex from U to V-U or vice versa
        for i in range(n):
            new_U = current_U[:]
            new_U[i] = 1 - new_U[i]
            visited = [False] * (n + 1)
            new_cut = dfs(1, new_U, visited, 0) if not visited[1] else count_cut_edges(new_U)
            heapq.heappush(pq, (-new_cut, new_U[:]))

    return max_cut_edges, best_U

# Read input from file
with open('input.txt', 'r') as f:
    n, m = map(int, f.readline().split())
    graph = Graph(n)
    for _ in range(m):
        u, v = map(int, f.readline().split())
        graph.add_edge(u, v)

# Compute max cut
max_cut_edges, best_U = max_cut(graph, n)

# Write output to file
with open('output.txt', 'w') as f:
    f.write(f"{max_cut_edges}\n")
    f.write(" ".join(map(str, best_U)) + "\n")
